import java.util.*;

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //这个二叉树的根节点
    //public TreeNode root;
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        // E.right = H;
        return A;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null || subRoot == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        if (isSubtree(root.left, subRoot)) {
            return true;
        }
        if (isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }

    //字节原题
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        if (left >= 0 && right >= 0 && Math.abs(left - right) <= 1) {
            return Math.max(left, right) + 1;//高度
        } else {
            return -1;
        }
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return maxDepth(root) >= 0;
    }

    //判断对称
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    private boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree == null && rightTree != null
                || leftTree != null && rightTree == null) {
            return false;
        }
        if (leftTree == null && rightTree == null) {
            return true;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left, rightTree.right) &&
                isSymmetricChild(leftTree.right, rightTree.left);
    }

    //层序遍历
    void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    /*    public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> ret = new ArrayList<>();
            if(root == null){
                return ret;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                //row为一行的数据
                List<Integer> row = new ArrayList<>();
                //确定一层的数据
                while(size > 0){
                    TreeNode cur = queue.poll();
                    row.add(cur.val);
                    if(cur.left != null){
                        queue.offer(cur.left);
                    }
                    if(cur.right != null){
                        queue.offer(cur.right);
                    }
                    size--;
                }
                //添加一层的数据
                ret.add(row);
            }
            return ret;
        }*/
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp != null) {
                return false;
            }
        }
        return true;
    }

    //求最近公共祖先（搜索二叉树）
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
        if (leftTree != null && rightTree != null) {
            return root;
        } else if (leftTree != null) {
            return leftTree;
        } else {
            return rightTree;
        }
    }

    //求最近公共祖先（非搜索二叉树）
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        Stack<TreeNode> leftStack = new Stack<>();
        getPath(root, p, leftStack);

        Stack<TreeNode> rightStack = new Stack<>();
        getPath(root, p, rightStack);
        //谁大，谁先多余路径走掉
        if (leftStack.size() > rightStack.size()) {
            int sz = leftStack.size() - rightStack.size();
            while (sz > 0) {
                leftStack.pop();
                sz--;
            }
        } else {
            int sz = rightStack.size() - leftStack.size();
            while (sz > 0) {
                rightStack.pop();
                sz--;
            }
        }
        //两个一起出栈，遇到相同部分停下，相同部分即为公共结点
        while (!leftStack.empty() && !rightStack.empty()) {
            TreeNode leftTree = leftStack.pop();
            TreeNode rightTree = rightStack.pop();
            if (leftTree.val == rightTree.val) {
                return leftTree;
            }
        }
        return null;//没有公共祖先
    }

    //找到指定结点的路径,将路径压入栈中
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null || node == null) {
            return false;
        }
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean ret1 = getPath(root.left, node, stack);
        if (ret1) {
            return true;
        }
        boolean ret2 = getPath(root.right, node, stack);
        if (ret2) {
            return true;
        }
        stack.pop();
        return false;
    }

    //将二叉搜索树转化成一个有序的链表
    TreeNode prev = null;

    public TreeNode createList(TreeNode root) {
        if (root == null) {
            return null;
        }
        createList(root.left);
        root.left = prev;
        if (prev != null) {
            prev.right = root;
        }
        prev = root;
        createList(root.right);
        return root;//最后返回根结点
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        TreeNode head = createList(pRootOfTree);
        //需要遍历到链表的头节点
        while (head.left != null) {
            head = head.left;
        }
        return head;
    }

    //根据前序遍历和中序遍历构建二叉树
/*    public int preIndex;

    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegan, int inEnd) {
        //如果ib > ie说明递归终止
        if (inBegan > inEnd) {
            return null;
        }
        //创建根节点
        TreeNode root = new TreeNode(preorder[preIndex]);
        //在中序遍历中找到对应的根节点下标
        int InorderIndex = fundInorderIndex(inorder, preorder[preIndex], inBegan, inEnd);
        //前序遍历中的下标继续往后遍历
        preIndex++;
        //通过递归继续创建左子树和右子树
        root.left = buildTreeChild(preorder, inorder, inBegan, InorderIndex - 1);
        root.right = buildTreeChild(preorder, inorder, InorderIndex + 1, inEnd);
        //最后返回根结点即可
        return root;
    }

    public int fundInorderIndex(int[] inorder, int val, int inBegan, int inEnd) {
        for (int i = inBegan; i <= inEnd; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        StringBuilder ret = new StringBuilder();
        ret.append(1);

        return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
    }*/
/*    public String tree2str(TreeNode root) {
        StringBuilder ret = new StringBuilder();
        tree2strChild(root, ret);
        return ret.toString();
    }
    public void tree2strChild(TreeNode root, StringBuilder ret) {
        if(root == null){
            return ;
        }
        ret.append(root.val);
        if(root.left != null){
            ret.append("(");
            tree2strChild(root.left, ret);
            ret.append(")");
        }else{
            if(root.right == null){
                return;
            }else{
                ret.append("()");
            }
        }
        if(root.right != null){
            ret.append("(");
            tree2strChild(root.right ,ret);
            ret.append(")");
        }else{
            return;
        }
    }*/
    public String tree2str(TreeNode root) {
        StringBuilder str = new StringBuilder();
        tree2strChild(root, str);
        return str.toString();
    }
    public void tree2strChild(TreeNode root, StringBuilder str){
        if(root == null){
            return;
        }
        str.append(root.val);
        if(root.left != null){
            str.append("(");
            tree2strChild(root.left, str);
            str.append(")");
        }else{
            if(root.right != null){
                str.append("()");
            }else{
                return;
            }
        }
        if(root.right != null){
            str.append("(");
            tree2strChild(root.right, str);
            str.append(")");
        }else{
            return;
        }
    }
/*    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.empty()){
            while(cur != null){
                stack.push(cur);
                ret.add(cur.val);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
    return ret;

    }*/
}